//
//  XBSortExample.c
//  数据结构算法和笔试题
//
//  Created by 王国栋 on 16/6/25.
//  Copyright © 2016年 xiaobai. All rights reserved.
//

#include "XBSortExample.h"
// 看到很多笔试题都是和排序相关的，这里要和排序做个了断！！

/*

排序：个人理解就是把无序的数据按照某个关键字，进行从小到大或者从大到小排序

这两点以前确实没有想过
排序稳定性：稳定性是指关键字相同的数据，在排序完成后位置会不会发生变化。比如现在一个成绩单，A的成绩是86，B的成绩也是86，现在分别位于
 
数组的第10个位置，和第11个位置。当然还有很多其他的人成绩，比如一共50个人。在对这50个人排序的完成后，A的位置会不会和B的位置交换。
如果发生了交换B出现在了A前面，不是按照原来的先后顺序了，发生这样的情况就是不稳定的排序。如果排序后相同的关键字所在的位置的先后顺序并没有
发生变化就是稳定的排序。
 
内排序和外排序
 
排序过程中待排序的数据是否全部被放置在内存中，排序分为内排序和外排序。内排序所有的数据必须全部放在内存中，外排序是排序记录的个数太多，内存放不下
 
需要在内外村多次交换数据才行。
 
 影响内排序的性能:
 1.时间
 主要是比较和移动，高效率的排序算法应该是尽量少的移动和比较次数
 
 2.空间 
 空间包括存放数据所需要的空间还有其他的辅助空间
 
 3.算法复杂性
 这里是算法本身的复杂度。
 
*/

// 1----- 内排序算法（插入，交换，选择和归并）

//1.1 冒泡排序


XBArrayList  sortL;

void createTestL()
{
    DATATYPE originA[] = {9,5,7,6,4,8,1,3,2};
    initXBArrayList(& sortL);//初始化
    //插入元素
    printf("开始添加元素:\n");
    for (int i = 0; i<10; i++) {
        
        addItemToXBArrayList(&sortL,originA[i]);//添加元素
    }
    printf("排序前:\n");
    printXBArrayListData(sortL);

}
//这里就相当于简单的交换顺序排序，不是真正意义的冒泡排序
void swapSort(XBArrayList * L)
{
    
    for (int i =0 ; i<L->length; i++) {
        
        for (int j = i+1; j<L->length; j++) {//第i次移动能够保证第i大的数在目标位置上，所以满足length-i-1就可以
            
            if (L->data[i]>L->data[j]) {
                
                swapXBArrayList(L, i, j);
            }
        }
        
    }
    printXBArrayListData(*L);
}




//相邻的两个数比较，大的向后移动
void bubbleSort(XBArrayList * L)
{
    
    for (int i =0 ; i<L->length; i++) {
        
        for (int j = 0; j<L->length-i-1; j++) {//第i次移动能够保证第i大的数在目标位置上，所以满足length-i-1就可以
            
            if (L->data[j]>L->data[j+1]) {
                
                swapXBArrayList(L, j, j+1);
            }
        }
        
    }
    printXBArrayListData(*L);
}

// 冒泡算法的优化

//相邻的两个数比较，大的向后移动
void bubbleSort2(XBArrayList * L)
{
    
    int flag =1;//增加一个标志位 可以减少没有意义的判断
    for (int i =0 ; i<L->length&&flag==1; i++) {
        
        flag = 0;
        for (int j = 0; j<L->length-i-1; j++) {//第i次移动能够保证第i大的数在目标位置上，所以满足length-i-1就可以
            
            if (L->data[j]>L->data[j+1]) {// 如果在某次循环中没有一次进行交换，说明这里的数据本来就是有序的了，无需做无用功了
                
                swapXBArrayList(L, j, j+1);
                flag = 1;
            }
        }
        
    }
    printXBArrayListData(*L);
}

// 冒泡排序复杂度：改进后的，最好的情况下没有数据要交换就是需要进行n-1次比较，所以时间复杂度是O(n)
//最坏的情况下，数据都是逆序的，一次交换都不会少复杂度是O(n^2）

//1.2 简单选择排序

//思路：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列的第i个记录。
void selectSort (XBArrayList * L)
{
    int min,j;
    for (int i = 0; i<L->length; i++) {
        
        min = i; //假设当前的数据的下标为最小的下标
        for (j=i+1; j<L->length; j++) {
            
            if (L->data[min]>L->data[j]) {
                
                min = j; //如果有当前的下标小的数,
            }
        }
        if (j!=min) {
            
            swapXBArrayList(L, min,i);//若不等于i说明找到最小值了就进行交换。
        }
    }
    printXBArrayListData(*L);

}
// 选择排序交换的次数非常少。交换次树等于外部循环的次数。节约了很多时间。无论最好还是最坏。比较的次数是一样的第i趟排序需要进行n-i
//次关键字比较，一共需要n*(n-1)/2次。对于交换次数，最好时候是0次。最差的时候是n-1次。所以时间复杂度为O（n^2)但是因为交换的次数少
//性能高于冒泡排序


//1.3 直接插入排序

//思路：讲一个记录直接插入到已经排好序的有序表中。

void insertSort(XBArrayList * L)
{
    
    int i,j,t;
    for (i = 1;i<L->length; i++) {
        
        if (L->data[i]<L->data[i-1]) {//后面的数据小于前面的数据说明位置反了。需要插入到有序的序列。0 - i-1的都是有序的
            
            t = L->data[i];
            for (j = i-1; L->data[j]>t&&j>=0; j--) {//在0和i-1之间的合适的位置插入
                
                L->data[j+1] = L->data[j];
            }
            L->data[j+1] = t;
            
        }
    }
    printXBArrayListData(*L);

}

// 复杂度分析。当排序本身有序的时候知识进行了比较n-1次，并没有一次插入。时间复杂度是O(n).最坏的情况下逆序的情况 2+3+..n 次O(n^2)，平均比较和移动次数大约是n^2/4，所以插入排序比选择和冒泡要好


// 1.4 希尔排序

/*
 
希尔排序法让待排序的记录个数减少，将原来的大量记录数的记录分割成多个组，保证每个组基本有序。基本有序是小的关键字基本在前面，
 大的基本在后面，{2，1，3，6，4，7，5，8，9}就可以称为基本有序。{1，5，9，，3，8，7，2，4，6}就不能。
 希尔排序采用了分割跳跃的策略，将相聚某个增量的记录组成一个子序列，在子序列内分别进行直接插入得到基本有序的结果。
 
*/

void ShellSort(XBArrayList *L)
{

    int i,j,t;
    int increment = L->length;//通过设置了increment，作为步数。达到先构建局部有序的，局部的操作是插入排序
    do {
        
        increment = increment/3;
        for (i = increment+1; i<L->length; i++) {
            
            if (L->data[i]<L->data[i-increment]) {
                
                t = L->data[i];
                for (j=i-increment; j>=0&&t<L->data[j]; j-=increment) {
                    
                    L->data[j+increment] = L->data[j];
                }
                L->data[j+increment] =t ;
            }
        }
        
    } while (increment>1);
    
    printXBArrayListData(*L);

}
/*
 复杂度分析：
 希尔排序是根据子序列实现跳跃式移动，提高效率的，增量的选取还是数学难题，大量研究表明dlta[k]=2^(T-K+1)-1的时候可以取的不错效果。
 算复杂度为O(n^2)
 希尔排序不稳定
 */

// 归并排序
/*
 归并排序是利用归并的思想进行排序，假设排序序列有n个记录，可以看成n个有序序列，每个子序列的两两合并得到n/2向上取整个有序子序列，然后两两合并
 
 直到得到一个长度为n的有序序列。
 
 */
void mergeSort(int SR[],int TR[],int i,int m,int n)
{
    int j,k,l;
    for (j=m+1,k=1; i<=m&&j<=n; i++) {
        
        if (SR[i]<SR[j]) {
            
            TR[k]=SR[i++];
        }
        else
        {
            TR[k]=SR[j++];
        }
    }
    if (i==m) {
        
        for (l=0; l<=m-i; l++) {
            
            TR[k+1]=SR[i+1];
        }
    }
    if (j<=n) {
        
        for (l=0; l<=n; l++) {
            TR[k+1] = SR[j+1];
        }
    }
    
}


void Msort(int SR[],int TR1[],int s,int t)
{
    int m;
    int TR2[MAX_SIZE];
    if (s==t) {
        
        TR1[s]=SR[s];
    }
    else
    {
        m = (s+t)/2;
        Msort(SR, TR2, s, m);
        Msort(SR, TR2, m+1, t);
        
    }
}

// ----- 快速排序
/*
 通过一趟排序将待排序的待排序纪录分成独立的两部分，其中一部分纪录的关键字比另一部分都小。可分别对这两部分纪录进行排序，以达到排序目的，
 基准数是任意的，但是为了方便和递归方便，所以找可以选择最左边的,基准数是最左边的时候要从最右边开始寻找进行j--。
 这是为了保证一定会停在比基准数大的位置上。
 
 快速排序的性能取决于排序的递归的深度
 */

void XBQsort(XBArrayList * L,int start,int end)
{
    
    if (start>end) {
       // printXBArrayListData(*L);
        return;
    }
    int base = L->data[start];
    int i = start;
    int j = end;
    while (i!=j) {
        
        while (L->data[j]>=base&&j>i) {//右边找一个小的数，基准
            j--;
        }
        while (L->data[i]<=base&&i<j) {//左端找一个大的数
            i++;
        }
        swapXBArrayList(L,i, j);//交换两个数的位置
    }
    if (i<j) {
        swapXBArrayList(L, start, i);
    }
    
    swapXBArrayList(L, start, i);
    XBQsort( L, start,i-1);
    XBQsort (L, i+1 ,end);

}













